from typing import List


class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        if nums[len(nums)-1]!=len(nums):return len(nums)
        if nums[0]==1:return 0
        start=0
        end=len(nums)-1
        while end-start>1:
            mid=int(start+(end-start)/2)
            if nums[mid]==mid:start=mid
            if nums[mid]==mid+1:end=mid
        return end


if __name__ == '__main__':
    s=Solution()
    nums=[1,2,3]
    ans=s.missingNumber(nums)
    print(ans)